/*
 * @lc app=leetcode.cn id=449 lang=golang
 * @lcpr version=30118
 *
 * [449] 序列化和反序列化二叉搜索树
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	// 先序遍历
	preorder := "," // 为了方便后文重构时的搜索
	preorderTraversal(root, &preorder)
	preorder += "|"

	// 中序遍历
	inorder := "," // 为了方便后文重构时的搜索
	inorderTraversal(root, &inorder)

	return preorder + inorder + "|" + strconv.Itoa(len(preorder))
}

func preorderTraversal(root *TreeNode, xianxu *string) {
	if root == nil {
		*xianxu += "#,"
		return
	}
	*xianxu += strconv.Itoa(root.Val) + ","
	preorderTraversal(root.Left, xianxu)
	preorderTraversal(root.Right, xianxu)
	return
}

func inorderTraversal(root *TreeNode, zhongxu *string) {
	if root == nil {
		*zhongxu += "#,"
		return
	}
	inorderTraversal(root.Left, zhongxu)
	*zhongxu += strconv.Itoa(root.Val) + ","
	inorderTraversal(root.Right, zhongxu)
	return
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	var preorder, inorder string
	{
		i := len(data) - 1
		for ; i >= 0 && data[i] != '|'; i-- {
		}
		len_xianxu, err := strconv.Atoi(data[i+1:])
		if err != nil {
			panic(err)
		}
		preorder = data[:len_xianxu-1]
		inorder = data[len_xianxu:i]
	}

	return this.construct(preorder, inorder)
}

func (this *Codec) construct(preorder, inorder string) *TreeNode {
	// fmt.Println("preorder:", preorder)
	// fmt.Println("inorder:", inorder)

	if preorder[1] == '#' {
		return nil
	}
	i := 1
	for preorder[i] != ',' {
		i++
	}
	val, err := strconv.Atoi(preorder[1:i])
	if err != nil {
		panic(err)
	}

	// fmt.Printf("val: %d\ti: %d\n", val, i)

	root := &TreeNode{val, nil, nil}

	idx := strings.Index(inorder, preorder[0:i+1])
	root.Left = this.construct(preorder[i:], inorder[0:idx+1])

	root.Right = this.construct(preorder[i+idx:], inorder[idx+i:])
	return root
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor()
 * deser := Constructor()
 * tree := ser.serialize(root)
 * ans := deser.deserialize(tree)
 * return ans
 */
// @lc code=end

/*
// @lcpr case=start
// [2,1,3]\n
// @lcpr case=end

// @lcpr case=start
// []\n
// @lcpr case=end

*/

